package dynamicProgramming.bagQuestion;

//
//给定 n 种物品, 每种物品都有无限个. 第 i 个物品的体积为 A[i], 价值为 V[i].
//
//        再给定一个容量为 m 的背包. 问可以装入背包的最大价值是多少?


public class Bag03 {


    public int backPackIII(int[] a, int[] v, int m) {
        int[][]dp=new int[a.length+1][m+1];
        for (int index = 1; index<=a.length; index++) {
            for (int rest = 1; rest <=m; rest++) {
                if (a[index-1]>rest){
                    dp[index][rest]=dp[index-1][rest];
                }else {
                    //TODO:2024/1/24  开心  写出来了
                    for (int i = 1; i * a[index - 1] <= rest; i++) {
                        dp[index][rest] = Math.max(v[index - 1] + dp[index][rest - i * a[index - 1]], Math.max(dp[index - 1][rest], dp[index][rest]));
                    }
                }
            }
        }
        return  dp[a.length][m];

    }

    public static void main(String[] args) {
        Bag03 bag03 = new Bag03();
       int[]a= {2,3,5,7};
       int[] v={1,5,2,4};
        int i = bag03.backPackIII(a, v, 10);
        System.out.println(i);
    }

}
